#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

void printTable(const vector<vector<int>>& matr) {
	printf("   ");
	for (int j = 0; j < matr[0].size(); ++j) {
		printf("%3d", j);
	}
	printf("\n");
	
	for (int i = 0; i < matr.size(); ++i) {
		printf("%3d", i);
		for (int j = 0; j < matr[i].size(); ++j) {
			printf("%3d", matr[i][j]);
		}
		printf("\n");
	}
}

void findAns(const vector<vector<int>>& matr, vector<int>& ans, 
             const vector<int>& w, int k, int s) {
	if (matr[k][s] == 0) 
		return;
	if (matr[k - 1][s] == matr[k][s])
		findAns(matr, ans, w, k - 1, s);
	else {
		findAns(matr, ans, w, k - 1, s - w[k]);
		ans.push_back(k);
	} 
}

int main() {
	// your code goes here
	int n, C;          // —èñëî ïðåäìåòîâ è ìàêñèìàëüíûé âåñ
	cin >> n >> C;
	vector<int> c(n+1), w(n+1);   // ‘òîèìîñòü ïðåäìåòîâ è èõ âåñà
	vector<vector<int>> matr(n+1, vector<int>(C+1));
	for (int i = 1; i <= n; ++i) {
		cin >> c[i] >> w[i];
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= C; ++j) {
			if (j < w[i]) matr[i][j] = matr[i-1][j];
			else matr[i][j] = max(matr[i-1][j], matr[i-1][j-w[i]] + c[i]);
		}
	}
	printTable(matr);
	vector<int> ans;
	findAns(matr, ans, w, n, C);
	cout << "‚ ðþêçàê âîøëè ïðåäìåòû: ";
	for (auto el: ans) cout << el << ", ";
	return 0;
}

ïðèìåð ââîäà
2 5
5 4
3 3
2 ïðåäìåòà 
ìàêñèìàëüíûé âåñ 5
öåíà 5 è 4
âåñà 3 è 3